package com.zhang.heap;

import com.zhang.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @author 张吉鑫
 * @Description 二叉堆
 * @date 2021/4/5 17:42
 */
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;

    public BinaryHeap(E[] elements,Comparator comparator){
        super(comparator);
        if (elements == null || elements.length == 0){
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        }else {
            int length = elements.length;
            int capacity = Math.max((length + (length << 1)), DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < length; i++) {
                this.elements[i] = elements[i];
            }
            size = length;
            heapify(this.elements);
        }
    }

    public BinaryHeap(E[] elements){
        this(elements,null);
    }

    public BinaryHeap() {
        this(null,null);
    }

    public BinaryHeap(Comparator comparator) {
        this(null,comparator);
    }


    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);

        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        E root = elements[0];
        size--;
        elements[0] = elements[size];
        elements[size] = null;

        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = elements[0];
        elements[0] = element;
        if (size == 0){
            size++;
        }else {
            siftDown(0);
        }
        return root;
    }

    /**
     * 批量建堆
     * @param elements
     */
    private void heapify(E[] elements) {
        //自上而下的上滤
        /*for (int i = 1; i < size; i++) {
            siftUp(i);
        }*/
        //自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int i = size >> 1;
        while (index < i) {
            int leftIndex = (index << 1) + 1;
            E leftElement = elements[leftIndex];

            int rightIndex = leftIndex + 1;
            if (rightIndex < size && (compare(elements[rightIndex],leftElement) > 0)){
                leftElement = elements[leftIndex = rightIndex];
            }

            if (compare(element, leftElement) >= 0) {
                break;
            }
            elements[index] = leftElement;
            index = leftIndex;
        }
        elements[index] = element;
    }

    /**
     * 上滤
     * @param index
     */
    private void siftUp(int index) {
        E e = elements[index];
        while (index > 0) {
            int i = (index - 1) >> 1;
            E p = elements[i];
            if (compare(e, p) <= 0) {
                break;
            }
            elements[index] = p;

            index = i;
        }
        elements[index] = e;
    }

    /**
     * 动态扩容
     *
     * @param capacity 预计元素长度
     */
    private void ensureCapacity(int capacity) {
        int length = elements.length;
        if (length >= capacity) {
            return;
        }
        int newLength = length + (length >> 1);
        E[] newElements = (E[]) new Object[newLength];
        for (int i = 0; i < length; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(length + "扩容为=>" + newLength);
    }

    /**
     * 检查数组是否为空
     */
    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }

    /**
     * 检查元素不能为空
     *
     * @param element
     */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public java.lang.Object root() {
        return 0;
    }

    @Override
    public java.lang.Object left(java.lang.Object node) {
        int index = (int) node;
        int i = (index << 1) + 1;
        return i >= size ? null : i;
    }

    @Override
    public java.lang.Object right(java.lang.Object node) {
        int index = (int) node;
        int i = (index << 1) + 2;
        return i >= size ? null : i;
    }

    @Override
    public java.lang.Object string(java.lang.Object node) {
        int index = (int) node;
        return elements[index];
    }
}
